package com.myc.subjects.binarytreeandrecurtion;

/**
 * 对于树结构的遍历和处理，最为常用的代码结构就是递归（Recursion）。
 * 递归是一种重要的编程技术，该方法用来让一个函数（方法）从其内部调用其自身。一个含直接或间接调用本函数语句的函数，被称之为递归函数。
 * 递归的实现有两个必要条件：
 * 必须定义一个“基准条件”，也就是递归终止的条件。在这种情况下，可以直接返回结果，无需继续递归
 * 在方法中通过调用自身，向着基准情况前进
 *
 * 一个简单示例就是计算阶乘：0 的阶乘被特别地定义为 1；n的阶乘可以通过计算 n-1的阶乘再乘以n来求得的。
 *
 * 下面的第二种实现，把递归调用置于函数的末尾，即正好在return语句之前，这种形式的递归被称为尾递归 (tail recursion)，其形式相当于循环。
 * 一些语言的编译器对于尾递归可以进行优化，节约递归调用的栈资源。(java不可以)
 */

public class Digui {

    //递归
    public int factorial(int n){
        if(n == 0) return 1;
        return factorial(n - 1) * n;
    }

    //尾递归
    public int factorial(int n, int acc){//将上一步计算结果作为参数acc
        if(n == 0) return acc;
        return factorial(n - 1, acc * n);//递归调用直接作为返回值
    }

    public static void main(String[] args) {
        int n = 6;
        Digui d = new Digui();
        System.out.println(d.factorial(n));
        System.out.println(d.factorial(n, 1));
    }

}
